The present invention relates to digital data transmission and, in particular, to error correcting codes.
Continued advances in forward error-correcting codes, such as convolutional codes and trellis codes, have enabled designers of modems, wireless communications systems and other digital communications systems to achieve increased bit rates for a given level of error rate performance. Among the various innovations that have been introduced over the years are so-called turbo codes. At the heart of the turbo code concept is the encoding of input data using more than one encoder combined with an interleaver in such a way that improved performance (as compared to a single encoding) can be achieved using a corresponding number of so-called soft input/soft output decoders which operate iteratively.
An early description of turbo codes appears in C. Berrou, et al, xe2x80x9cNear Shannon limit error-correcting coding and decoding: Turbo codes,xe2x80x9d Proc. 1993 Int. Conf Communication (Geneva, Switzerland, May 1993), pp. 1064-1070. Berrou et al discloses a so-called parallel-concatenated turbo code. The input data is applied to a first convolutional encoder and an interleaved version of the input data is applied to a second convolutional encoder. The output bits of the two encoders are then mapped into signal points of a two-dimensional (2D) 4-PSK signaling constellation for transmission. Some of the redundant bits generated by the encoders may be subjected to a so-called puncturing prior to the mapping step in order to improve bandwidth efficiency (measured in bits per 2D signal point).
At relatively high error rates, a parallel concatenated turbo code provides excellent coding gain, thereby advantageously reducing the level of received signal-to-noise ratio required in order to realize a desired level of error rate performance. Disadvantageously, however, achieving that excellent coding gain requires an extremely long interleaver. This introduces significant end-to-end delay, or latency, which is undesirable in many applications. Moreover, a parallel-concatenated turbo code exhibits a so-called error floor phenomenon wherein the improvement in coding gain is far less dramatic at lower error rates and, indeed, may be comparable to, or even worse than, that achieved using more conventional encoding and decoding.
Also known in the prior art are so-called serial-concatenated turbo codes, as disclosed, for example, by S. Benedetto, et al, xe2x80x9cSerial concatenation of interleaved codes: Performance analysis, design, and iterative decoding,xe2x80x9d IEEE Trans. Inform. Theory, vol. 44, pp. 909-926, May 1998. Here, the input data is applied to a first convolutional encoder and the output bits of the first encoder, after interleaving, are used as the input bits for a second convolutional encoder. The output bits of the second encoder are then mapped into signal points of a 2D 4-PSK signaling constellation for transmission. The above-mentioned error floor phenomenon is less pronounced for serial-concatenated turbo codes than for parallel-concatenated turbo codes, thereby providing better coding gain at lower error rates. However, these serial-concatenated turbo codes generate more redundant bits than in the parallel case, so that they are less bandwidth-efficient. Moreover, they too require a long interleaver.
Neither the parallel-concatenated, nor the serial-concatenated turbo codes described in the above-discussed prior art references are bandwidth efficient; each of them has a bandwidth efficiency of less than two bits per 2D signal point. More bandwidth-efficient parallel concatenated turbo codes are known, however. See, for example, S. Benedetto, et al, xe2x80x9cBandwidth efficient parallel concatenated coding schemes,xe2x80x9d Electron. Lett., vol. 31, pp. 2067-2069, 1995, and P. Robertson, et al, xe2x80x9cCoded modulation scheme employing turbo codes,xe2x80x9d Electron. Lett., vol. 31, pp. 1546-1547, 1995. The arrangements disclosed in these references achieve high coding gains at high error rate while featuring an improved bandwidth efficiency of a full 2 bits per 2D signal point by using rate-⅔ trellis codes designed jointly with a 2D 8-PSK signaling constellation rather than the convolutional codes with a 2D 4-PSK constellation used in the Berrou arrangement. However, these latter codes still exhibit the above-mentioned error floor phenomenon and long delays.
The prior art also teaches that another way of achieving increased bandwidth efficiency while achieving the advantages of the turbo code approach is to employ so-called multi-level coding in which the code used in at least one of the levels is a parallel-concatenated turbo code of the kind disclosed by Berrou. (As is well known, a multilevel code is one in which the output bits of different codes are used to select increasingly finer subsets, and ultimately a single signal point, of the signal constellation.) Such a code is disclosed in U. Wachsmann, et al, xe2x80x9cPower and bandwidth efficient digital communication using turbo codes in multilevel codes,xe2x80x9d Euro. Trans. Telecommun., vol. 6, pp. 557-567, September 1995. However, the error floor and delay characteristics of such a multi-level code promise to be no betterxe2x80x94and may prove to be worsexe2x80x94than that of the parallel-concatenated turbo code used in a non-multi-level-coding arrangement.
There has remained a need in the art for turbo coding arrangements which exhibit turbo codes"" advantageous error rate performance, achieve high bandwidth efficiency, low delay and less pronounced error floor, while yet involving an acceptable level of decoding complexity.
Turbo codes embodying the principles of the invention are serial-concatenated codes, herein defined to mean turbo codes for which at least some of the output bits, including at least one redundant bit, provided by a first, outer encoder are further processed, after interleaving, by a second, inner encoder. The present turbo codes may be of any desired dimensionality, Nxe2x89xa71, meaning that the data to be transmitted is represented by an N-tuple, or N-dimensional symbol, whose N coordinates are selected by the output bits of the encoders interdependently. For example, when N is an even integer, an N-dimensional symbol may be conveniently transmitted, during an N-dimensional xe2x80x9csymbol interval,xe2x80x9d as a combination of N/2 2D signal points, wherein each so-called signal space coordinate of the 2D signal point is represented, during a 2D xe2x80x9csignaling interval,xe2x80x9d by the amplitude of an in-phase or quadrature-phase component of a modulated carrier signal. Thus the aforementioned symbol interval is made up of N/2 signaling intervals. For the code where N=2, the symbol interval and the signaling interval are the same.
More specifically, in turbo codes embodying the principles of the invention a) the state of each of the inner and outer encoders is advanced only once per symbol interval, and b) all of the data bits, and at least one redundant bit generated by one or both of the encoders for that symbol interval are transmitted together during a single symbol interval, and c) the inner and outer encoders are trellis encoders. This approach advantageously provides turbo codes having a lower delay than the prior art arrangements and, in addition, affords an advantageous combination of error rate performance, bandwidth efficiency, and decoder complexity not achieved by prior art arrangements and exhibiting a less pronounced (or perhaps no) error floor. The inner and outer codes may be of any desired dimensionality.
Arrangements embodying the principles of the invention utilize a signal constellation of sufficient size (i.e., number of symbols in the constellation) to accommodate the transmission of the data bits and redundant bits within the aforementioned single symbol interval. Moreover, in preferred embodiments, the turbo code, the constellation, and the mapping between the bits to be transmitted and the constellation symbols are selected in view of the one another in such a way that the code complexity and interleaving delay necessary to achieve a given level of error rate performance are less than they would be if the turbo code, constellation and mapping were not selected in view of one another. This is referred to in the art as a xe2x80x9cjoint design,xe2x80x9d as more formally defined hereinbelow.
In preferred embodiments, all the redundant bits generated by both the inner and outer encoders are transmitted (as compared to the puncturing approach used by Berrou et al in which not all the redundant bits are transmitted) , thereby taking advantage of the full amount of coding gain promised by the combined codes without sacrificing bandwidth efficiency. Although the prior art serial-concatenated codes can also transmit all the redundant bits generated by the encoders, they can do so only at the cost of substantially reduced bandwidth efficiency.
In preferred embodiments, less than all of the data bits processed by the outer encoder are further processed by the inner encoder. As compared to a case in which all of the data bits processed by the outer encoder are further processed by the inner encoder, this approach advantageously allows for a far less complex decoder and requires less delay while sacrificing, at most, a small amount of coding gain.
For various reasons, as described more fully hereinbelow, it may be advantageous to xe2x80x9cterminatexe2x80x9d the turbo code, meaning that both encoders are brought to a known state. In accordance with an advantageous aspect of the present invention, I have discovered that the overall turbo code can be terminated by terminating the outer and inner codes independently in distinct symbol intervals. In the illustrative embodiment, in particular, the state of the outer encoder is not advanced during symbol intervals in which the code of the inner encoder is being terminated.
In multidimensional embodiments of the invention as described above, i.e. for N greater than 2, the interleaver, in rearranging the outputs of the outer encoder, preferably uses as its interleaved elements the outer encoder outputs associated with a particular symbol interval, rather than, for example, the bits associated with the constituent signaling intervals of the symbol interval. I have found that such an approach advantageously drastically reduces the delay introduced by the interleaver and simplifies the steps required to terminate the turbo codes.
Arrangements embodying the principles of the invention may use the turbo-encoder output bits to identify a subset of the signal constellation and directly use yet other, uncoded bits to select a particular symbol from the identified subset. However, in order to realize the full coding gain offered by the turbo code, it may be desired to use a multi-level coding approach to encode at least some of those other bits using, for example, a simple parity check code, applying the design principles described in my U.S. Pat. No. 5,258,987 issued Nov. 2, 1993.